package cn.tedu.config;

public class HeapSort {

    public static void main(String[] args) {
        int[] array = {9, 2, 5, 1, 7, 4, 8, 3, 6};
        heapSort(array);

        System.out.println("Sorted array:");
        for (int num : array) {
            System.out.print(num + " ");
        }
    }
    public static void heapSort(int[] array) {
        int n = array.length;

        // 构建最大堆
        buildMaxHeap(array);

        // 依次取出堆顶元素，与堆末尾元素交换，并重新调整堆
        for (int i = n - 1; i > 0; i--) {
            // 将堆顶元素与堆末尾元素交换
            swap(array, 0, i);
            // 重新调整堆，将剩余元素构建成最大堆
            heapify(array, i, 0);
        }
    }

    private static void buildMaxHeap(int[] array) {
        int n = array.length;

        // 从最后一个非叶子节点开始，依次进行堆调整
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(array, n, i);
        }
    }

    private static void heapify(int[] array, int n, int i) {
        int largest = i; // 初始化最大值为根节点
        int left = 2 * i + 1; // 左子节点的索引
        int right = 2 * i + 2; // 右子节点的索引

        // 比较左子节点与根节点的值
        if (left < n && array[left] > array[largest]) {
            largest = left;
        }

        // 比较右子节点与当前最大值节点的值
        if (right < n && array[right] > array[largest]) {
            largest = right;
        }

        // 如果最大值不是根节点，则交换最大值与根节点的位置，并继续调整子堆
        if (largest != i) {
            swap(array, i, largest);
            heapify(array, n, largest);
        }
    }

    private static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }


}
